package LeetCode.rangeSumBST;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    int ans = 0;

    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) {
            return 0;
        }

        dfs(root, L, R);
        return ans;

    }

    public void dfs(TreeNode node, int L, int R) {
        if (node != null) {
            if (L <= node.val && node.val <= R) {
                ans += node.val;
                dfs(node.left, L, R);
                dfs(node.right, L, R);
            } else if (L > node.val) {
                dfs(node.right, L, R);
            } else if (node.val > R) {
                dfs(node.left, L, R);
            }

        }
    }
}